#include "stdafx.h"
#include <iostream>

#include <time.h>   
#include <ctime>
#include <stdio.h>      
#include <stdlib.h>   

using namespace std;




void shakeSort(int *a, const int n)
{
           int l, r, i, k, buf;
           k = l = 0;
           r = n - 2;
           while(l <= r)
           {
              for(i = l; i <= r; i++)
                 if (a[i] > a[i+1])
                 {
                    buf = a[i]; a[i] = a[i+1]; a[i+1] = buf;
                    k = i;
                 }
              r = k - 1;
              for(i = r; i >= l; i--)
                 if (a[i] > a[i+1])
                 {
                    buf = a[i]; a[i] = a[i+1]; a[i+1] = buf;
                    k = i;
                 }
              l = k + 1;
           }
        }